package medium;

import java.util.*;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2022/5/2 20:43
 */
public class No90_子集II {
    public static void main(String[] args) {
        Solution90 solution90 = new Solution90();
        int[] nums = new int[]{2,1,2};
        List<List<Integer>> lists = solution90.subsetsWithDup(nums);
        System.out.println(lists);
    }
}

class Solution90 {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        //No78_3.二进制标记
        //源数组排序
        //为了防止出现 212(011,110)这种情况
        Arrays.sort(nums);
        //规律:通过二进制右移判断1所在的索引
        // index = nums.length - 1 - move (右移位数)
        int allCheck = 1 << nums.length;
        
        Set<String> set = new HashSet<>();
        List<List<Integer>> res = new ArrayList<>();
        for (int check = 0; check < allCheck; check++) {
            // 0000 - 1111
            // 0110
            //通过右移位数
            String base = "";
            List<Integer> data = new ArrayList<>();
            for (int move = 0; move <= nums.length - 1; move++) {
                //右移结束的值
                int zhi = check >> move;
                //判断最右边是否是1
                if ((zhi & 1) != 0) {
                    //说明最右边是1
                    int index = nums.length - 1 - move;
                    //去重
                    base += nums[index] + "__啊啊啊啊啊";
                    data.add(nums[index]);
                }
            }
            if (set.add(base)) {
                //说明可以加
                res.add(data);
            }
        }
        return res;
    }
} 



    //public List<List<Integer>> subsetsWithDup(int[] nums) {
    //    //No46.全排列 参考
    //    //[1,2,2]
    //    
    //    //动态规划,定义dp[n]代表n-1索引位置数字进来时候的全子集
    //    List<List<Integer>>[] dp = new ArrayList[nums.length + 1];
    //    //dp[0]初始化,准备
    //    
    //    //dp[0]:  [[]]
    //    dp[0] = new ArrayList<>();
    //    dp[0].add(new ArrayList<>());
    //    
    //    //强行去重
    //    Set<String> set = new HashSet<>();
    //    //开始动态规划
    //    for (int i = 1; i <= nums.length; i++) {
    //        //计算dp[i]
    //        //[],[1],[2],[12] => [],[1],[2],[12] + ([],[1],[2],[12])+元素
    //        //当前元素(数字)
    //        int curData = nums[i - 1];
    //        //初始化dp[i]
    //        dp[i] = new ArrayList<>();
    //        //获取上一级大list
    //        // [],[1],[2],[12]
    //        List<List<Integer>> preListssssssssssss = dp[i - 1];
    //        //第一步: 上一层直接获取
    //        for (int j = 0; j < preListssssssssssss.size(); j++) {
    //            //[12]
    //            List<Integer> preList = preListssssssssssss.get(j);
    //            //值传递
    //            List<Integer> preListCopy = new ArrayList<>(preList);
    //            sortList(preListCopy);
    //            dp[i].add(preListCopy);
    //            //preListCopy的每一个元素的字符串
    //            String base = "";
    //            for (int k = 0; k < preListCopy.size(); k++) {
    //                String add = preListCopy.get(k) + "al;fjla";
    //                base += add;
    //            }
    //            set.add(base);
    //        }
    //        
    //        //第二步: 上一层+元素 直接获取
    //        for (int j = 0; j < preListssssssssssss.size(); j++) {
    //            //[12]
    //            List<Integer> preList = preListssssssssssss.get(j);
    //            //值传递
    //            List<Integer> preListCopy = new ArrayList<>(preList);
    //            //[12]->[122]
    //            preListCopy.add(curData);
    //            sortList(preListCopy);
    //            String base = "";
    //            for (int k = 0; k < preListCopy.size(); k++) {
    //                String add = preListCopy.get(k) + "al;fjla";
    //                base += add;
    //            }
    //            //第二步可能与第一步有重合
    //            if (set.add(base)) {
    //                dp[i].add(preListCopy);
    //            }
    //        }
    //        // [12] -> "12+?"
    //        // [21] -> [12] -> "12+?"
    //    }
    //    return dp[nums.length];
    //}
    //
    ////list排序
    //public void sortList(List<Integer> list) {
    //    list.sort(new Comparator<Integer>() {
    //        @Override
    //        public int compare(Integer o1, Integer o2) {
    //            return o1 > o2 ? 1 : -1;
    //        }
    //    });
    //}





